package com.csx.tree;

import com.csx.queue.LoopQueue;
import com.csx.stack.ArrayStack;
import com.csx.stack.Stack;

/**
 * @author 陈胤训
 * <p> 二分搜索树
 * create: 2019-05-09 11:02
 **/
public class BinarySearchTree<E extends Comparable<E>> {

    private class Node{
        public E e;

        public Node left, right;

        public Node(E e){
            this.e = e;
            left = null;
            right = null;
        }
    }

    private Node root;

    private int size;

    public BinarySearchTree(){
        root = null;
        size = 0;
    }

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    /**
     *  向二分搜索树中添加新的元素e
     * @param e 添加的内容
     */
    public void add1(E e){
        if (root == null){
            root = new Node(e);
            size ++;
        }else{
            add1(root,e);
        }
    }

    /**
     *  向二分搜索树中添加新的元素e  (改进)
     * @param e 添加的内容
     */
    public void add(E e){
        root = add(root,e);
    }

    /**
     * 向以node为根的二分搜索树中插入元素e, 递归算法
     * @param node
     * @param e
     */
    private void add1(Node node, E e){
         if (e.equals(node.e)){
             return;
         } else if (e.compareTo(node.e) < 0 && node.left == null){
            node.left = new Node(e);
            size ++;
            return;
         }else if (e.compareTo(node.e) > 0 && node.right == null){
             node.right = new Node(e);
             size ++;
             return;
         }

         if (e.compareTo(node.e) < 0){
             add1(node.left,e);
         }else{
             add1(node.right,e);
         }

    }

    /**
     * 向以node为根的二分搜索树中插入元素e, 递归算法  (改进版)
     * @param node
     * @param e
     * @return 返回插入新节点后二分搜索树的根
     */
    private Node add(Node node, E e){
        if (node == null){
            size ++;
            return new Node(e);
        }
        if (e.compareTo(node.e) < 0){
            node.left = add(node.left,e);
        }else if (e.compareTo(node.e) > 0){
            node.right = add(node.right,e);
        }
        return node;

    }

    /**
     * 查看二分搜索树中是否包含元素e
     * @param e
     * @return
     */
    public boolean contains(E e){
        return contains(root,e);
    }

    /**
     *  查看以node为根的二分搜索树中是否包含元素e,  递归算法
     * @param node
     * @param e
     * @return
     */
    private boolean contains(Node node, E e){
        if (node == null){
            return false;
        }
        if (e.compareTo(node.e) == 0){
            return true;
        }else if(e.compareTo(node.e) < 0){
            return contains(node.left,e);
        }else{
            return contains(node.right,e);
        }
    }

    /**
     * 二分搜索树的前序遍历
     */
    public void preOrder(){
        preOrder(root);
    }

    /**
     * 二分搜索树的前序遍历 以node为根的二分搜索树, 递归算法
     * @param node
     */
    private void preOrder(Node node){
        if (node == null){
            return;
        }
        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }

    /**
     * 二分搜索树非递归的前序遍历, 利用栈的结构算的
     */
    public void preOrderNR(){
        ArrayStack<Node> stack = new ArrayStack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            Node cur = stack.pop();
            System.out.println(cur.e);
            if (cur.right != null){
                stack.push(cur.right);
            }
            if (cur.left != null){
                stack.push(cur.left);
            }
        }
    }
    /**
     * 中序遍历
     */
    public void inOrder(){
        inOrder(root);
    }

    /**
     * 中序遍历 以node为根的二分搜索树,递归算法
     * @param root 根
     */
    private void inOrder(Node root) {
        if (root == null){
            return;
        }
        inOrder(root.left);
        System.out.println(root.e);
        inOrder(root.right);
    }

    /**
     * 后序遍历
     */
    public void postOrder(){
        postOrder(root);
    }

    /**
     * 后序遍历 以node为根的二分搜索树,递归算法
     * @param root 根
     */
    private void postOrder(Node root) {
        if (root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.e);
    }

    /**
     * 二分搜索树的层序遍历
     */
    public void levelOrder(){
        LoopQueue<Node> nodeLoopQueue = new LoopQueue<>();
        nodeLoopQueue.enqueue(root);
        while(!nodeLoopQueue.isEmpty()){
            Node cur = nodeLoopQueue.dequeue();
            System.out.println(cur.e);
            if (cur.left != null){
                nodeLoopQueue.enqueue(cur.left);
            }
            if (cur.right != null){
                nodeLoopQueue.enqueue(cur.right);
            }

        }
    }

    /**
     * 寻找二分搜索树最小值
     * @return 最小值
     */
    public E minimum(){
        if (size == 0){
            throw new IllegalArgumentException("BinarySearchTree is empty!");
        }
        return minimum(root).e;
    }

    /**
     * 返回以root 为根的二分搜索树的最小值所在的节点
     * @param root 根
     * @return 最小值所在的节点
     */
    private Node minimum(Node root) {
        if (root.left == null){
            return root;
        }
        return minimum(root.left);
    }

    /**
     * 寻找二分搜索树最大值
     * @return 最大值
     */
    public E maximum(){
        if (size == 0){
            throw new IllegalArgumentException("BinarySearchTree is empty!");
        }
        return maximum(root).e;
    }

    /**
     * 返回以root 为根的二分搜索树的最大值所在的节点
     * @param root 根
     * @return 最大值所在的节点
     */
    private Node maximum(Node root) {
        if (root.right == null){
            return root;
        }
        return maximum(root.right);
    }

    /**
     * 删除最小值所在的节点
     * @return 最小值
     */
    public E removeMin(){
        E minimum = minimum();
        root = removeMin(root);
        return minimum;
    }

    /**
     * 删除掉以node为根的二分搜索树中最小的节点
     * @param root 根
     * @return 返回新的根
     */
    private Node removeMin(Node root) {
        if (root.left == null){
            Node rightNode = root.right;
            root.right = null;
            size --;
            return rightNode;
        }
         root.left = removeMin(root.left);
        return root;
    }

    /**
     * 删除最大值所在的节点
     * @return 最大值
     */
    public E removeMax(){
        E maximum = maximum();
        root = removeMax(root);
        return maximum;
    }

    /**
     * 删除掉以node为根的二分搜索树中最大的节点
     * @param root 根
     * @return 返回新的根
     */
    private Node removeMax(Node root) {
        if (root.right == null){
            Node leftNode = root.left;
            root.left = null;
            size --;
            return leftNode;
        }
        root.right = removeMax(root.right);
        return root;
    }

    /**
     * 从二分搜索树中删除元素为e的节点
     * @param e 元素
     */
    public void remove(E e){
        root = remove(root,e);
    }

    /**
     * 删除掉以node为根的二分搜索树中值为e的节点, 递归算法
     * @param root 根
     * @param e 值
     * @return 删除以后的值
     */
    private Node remove(Node root, E e) {
        if (root == null){
            return null;
        }
        if (e.compareTo(root.e) < 0){
            root.left = remove(root.left,e);
            return root;
        }else if (e.compareTo(root.e) > 0){
            root.right = remove(root.right,e);
            return root;
        }else{
            if (root.right == null){
                Node leftNode = root.left;
                root.left = null;
                size --;
                return leftNode;
            }
            if (root.left == null){
                Node rightNode = root.right;
                root.right = null;
                size --;
                return rightNode;
            }
            /*
            *待删除节点左右子树均不为空的情况
            * 找到比待删除节点大的最小节点,  即待删除节点右子树的最小节点
            * 用这个节点顶替待删除节点的位置
            * */
            Node minimum = minimum(root.right);
            minimum.right = removeMin(root.right);
            minimum.left = root.left;
            root.left = root.right = null;
            return minimum;
        }
    }

    @Override
    public String toString(){
        StringBuilder builder = new StringBuilder();
        getBinarySearchTreeString(root,0,builder);
        return builder.toString();
    }

    private void getBinarySearchTreeString(Node root, int i, StringBuilder builder) {
        if (root == null){
            builder.append(getDepthString(i)+"null\n");
            return;
        }
        builder.append(getDepthString(i) + root.e + "\n");
        getBinarySearchTreeString(root.left,i+1,builder);
        getBinarySearchTreeString(root.right,i+1,builder);
    }

    private String getDepthString(int i) {
        StringBuilder builder = new StringBuilder();
        for (int j = 0; j < i ; j++) {
            builder.append("--");
        }
        return builder.toString();
    }

    public static void main(String[] args) {
        BinarySearchTree<Integer> tree = new BinarySearchTree<>();
        int[] nums = {5,3,6,8,4,2};
        for (int num :nums ) {
            tree.add(num);
        }
        tree.preOrder();
        System.out.println();
        tree.remove(5);

        tree.removeMax();
        tree.preOrderNR();
        System.out.println();

        tree.removeMax();
        tree.inOrder();
        System.out.println();

        tree.removeMax();
        tree.postOrder();
        System.out.println();

        tree.removeMax();
        tree.levelOrder();
//      System.out.println(tree);
    }
}
